package primary.code12_dp;

import lombok.extern.slf4j.Slf4j;

/**
 * 跑马
 * <p>
 * 自行搜索或者想象一个象棋的棋盘，然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置。
 * 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的一个区域。
 * 给你三个参数（x，y，k），返回如果 “马” 从(0,0)位置出发，必须走k步，最后落在(x,y)上的方法数有多少种？
 */
@Slf4j
public class Code04_HorseMove {

    /**
     * 潜台词：
     * 马从(0,0)位置出发
     * x的范围 0～8
     * y的范围 0～9
     */
    public static int horseMove(int x, int y, int k) {
        if (x < 0 || x > 8 || y < 0 || y > 9) {
            return 0;
        }
        if (k == 0) {
            return x == 0 && y == 0 ? 1 : 0;
        }
        return horseMove(x + 2, y + 1, k - 1) +
                horseMove(x + 2, y - 1, k - 1) +
                horseMove(x + 1, y + 2, k - 1) +
                horseMove(x + 1, y - 2, k - 1) +
                horseMove(x - 1, y + 2, k - 1) +
                horseMove(x - 1, y - 2, k - 1) +
                horseMove(x - 2, y + 1, k - 1) +
                horseMove(x - 2, y - 1, k - 1);
    }


    public static int horseMove2(int a, int b, int k) {
        int[][][] dp = new int[9][10][k + 1];
        dp[0][0][0] = 1; // base case
        for (int z = 1; z <= k; z++) {
            for (int x = 0; x < 9; x++) {
                for (int y = 0; y < 10; y++) {
                    dp[x][y][z] =
                                    getDpValue(dp, x + 2, y + 1, z - 1) +
                                    getDpValue(dp, x + 2, y - 1, z - 1) +
                                    getDpValue(dp, x + 1, y + 2, z - 1) +
                                    getDpValue(dp, x + 1, y - 2, z - 1) +
                                    getDpValue(dp, x - 1, y + 2, z - 1) +
                                    getDpValue(dp, x - 1, y - 2, z - 1) +
                                    getDpValue(dp, x - 2, y + 1, z - 1) +
                                    getDpValue(dp, x - 2, y - 1, z - 1);
                }
            }
        }
        return dp[a][b][k];
    }

    public static int getDpValue(int[][][] dp, int x, int y, int z) {
        if (x < 0 || x > 8 || y < 0 || y > 9) {
            return 0;
        }
        return dp[x][y][z];
    }


    public static void main(String[] args) {
        log.info("暴力递归方式, {}", horseMove(7, 7, 10)); // 515813
        log.info("DP方式, {}", horseMove2(7, 7, 10));
    }
}
